package org.example.sword2offer.primary;

import java.util.Arrays;

/**
 * @version 1.0.0
 * @author: lynn
 * @description: topk，堆排序实现，用大根堆,
 * https://www.bilibili.com/video/BV1UU4y1a7Vm?from=search&seid=14733331241947752939
 * @date: 2021/7/19 13:51
 */
public class Q89_TopKByHeap {
    public void heapSort(int[] array,int k){
        //[1] 先将数组转换为堆结构   k=8,我算出来是第一大的数
        //[4]实现一个循环，每一次都表示一个元素有序，每一次都将参与堆排序的数组最大下标向前提一个

        for (int end = array.length-1; end >=k ; end--) {
            //[2]将堆结构不断调整为大根堆
            maxHeap(array,end);
            //[3]将堆顶元素(此时表示的是堆当中最大的元素)和堆的最后一个叶子节点进行交换，代表这一轮堆排序完成
            int tmp=array[0]; //fixme 0和end交换
            array[0]=array[end];
            array[end]=tmp;
        }

    }


    /**
     * 构建大根堆，
     * array 是大根堆的数组
     * end 参与构建大根堆数组元素的最大坐标
     */
    private void maxHeap(int[] array,int end){
        //[1].根据公式计算出堆结构中最后一个父节点的下标
        //公式: lastFather =[(start+end)/2] 向上迁移 -1
        int lastFather=(0+end)%2!=0?(0+end)/2:(0+end)/2-1; //fixme 取余
        //[5] 从最后一个父亲节点开始向前不断的-1，使得每一个父节点都能够实现左右pk，以下犯上的步骤
        for (int father = lastFather; father >=0 ; father--) { //fixme 取余数
            //[2] 根据父节点的下标推算出左右孩子的数组下标
            //左孩子: 2n+1
            //右孩子: 2n+2
            int left=father*2+1;
            int right=father*2+2;
            //[3] 在保证右孩子下标没有越界的情况下，使用右孩子和父亲点进行比较
            if(right<=end && array[right]>array[father]){ //fixme right<end
                int tmp=array[right];
                array[right]=array[father];
                array[father]=tmp;
            }
            //[4] 使用左孩子和父节点进行比较，如果左孩子>父亲节点，进行交换
            //步骤[4]相当于间接进行了左右孩子的大小比较,left肯定在father的左边
            if (array[left]>array[father]){
                int tmp=array[left];
                array[left]=array[father];
                array[father]=tmp;
            }
        }
    }

    public static void main(String[] args) {
        int[] array=new int[]{0,2,3,1,4,8,9,6,5,7};
        System.out.println(Arrays.toString(array));
        Q89_TopKByHeap topKByHeap=new Q89_TopKByHeap();
        int k=7; // 得到的结果是 [1, 7, 4, 6, 2, 3, 0, 5, 8, 9], array[end]=9，但是我要得到第8大的数
        topKByHeap.heapSort(array,k);
        System.out.println(Arrays.toString(array));
        System.out.println(array[k]);//此时输出 7,此时后续的不需要排序;
        k=0; //此时退化为堆排，所有都排
        topKByHeap.heapSort(array,k);
        System.out.println(Arrays.toString(array));
    }
}

